"""
LCR 011. 连续数组
中等
相关标签
相关企业
给定一个二进制数组 nums , 找到含有相同数量的 0 和 1 的最长连续子数组，并返回该子数组的长度。



示例 1：

输入: nums = [0,1]
输出: 2
说明: [0, 1] 是具有相同数量 0 和 1 的最长连续子数组。
示例 2：

输入: nums = [0,1,0]
输出: 2
说明: [0, 1] (或 [1, 0]) 是具有相同数量 0 和 1 的最长连续子数组。


提示：

1 <= nums.length <= 105
nums[i] 不是 0 就是 1


注意：本题与主站 525 题相同： https://leetcode-cn.com/problems/contiguous-array/
"""
from typing import List


class Solution:
    def findMaxLength(self, nums: List[int]) -> int:
#         思路 ：如把0看作-1，1看作+1，那么在每一个前缀和相等节点之间。其01数量必然是相等的，因为前缀和的增长为0。有多少个1就必然有多少个-1
        count = 0
        maxlenth = 0
        # 字典形式为，cuont值:索引,为什么要把count作为k,索引为v？因为后面要运算maxlenth要计算两个相同值他们的索引之差，
#         也就是要找到知道值要找到索引，而字典一个v可以被多个k所对应。故把索引放到v。使得运算没有歧义
        prefixAdd = {0:-1}
        for index, num in enumerate(nums):
            if num:
                count +=1
            else:
                count -=1
            if count not in prefixAdd:
                prefixAdd[count] = index
            else:
                maxlenth=max(maxlenth,index - prefixAdd[count])
        # print(prefixAdd,maxlenth)
        return maxlenth
if __name__ == '__main__':
    print(Solution().findMaxLength([0,1]))